
#include <iostream>
#include <vector>
using namespace std;

  struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
 
 
class Solution {
public:
	TreeNode* build(vector<int>& inorder, vector<int>& postorder,int& idx,int midBegin,int midEnd){
		
		if(midBegin>midEnd){
			
			return nullptr;
		}
		TreeNode* root=new TreeNode(postorder[idx]);
		int rootIndx=midBegin;
		while(postorder[idx]!=inorder[rootIndx]){
			
			++rootIndx;
		}
		--idx;
		TreeNode* right=build(inorder,postorder,idx,rootIndx+1,midEnd);
		TreeNode* left=build(inorder,postorder,idx,midBegin,rootIndx-1);
		root->left=left;
		root->right=right;
		return root;
	}
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
      int idx=postorder.size()-1;
	  return build(inorder,postorder,idx,0,inorder.size()-1);  
    }
};
